﻿//你被请来给一个要举办高尔夫比赛的树林砍树。树林由一个 m x n 的矩阵表示， 在这个矩阵中：
//
//0 表示障碍，无法触碰
//1 表示地面，可以行走
//比 1 大的数 表示有树的单元格，可以行走，数值表示树的高度
//每一步，你都可以向上、下、左、右四个方向之一移动一个单位，如果你站的地方有一棵树，那么你可以决定是否要砍倒它。
//你需要按照树的高度从低向高砍掉所有的树，每砍过一颗树，该单元格的值变为 1（即变为地面）。
//你将从(0, 0) 点开始工作，返回你砍完所有树需要走的最小步数。 如果你无法砍完所有的树，返回 - 1 。
//可以保证的是，没有两棵树的高度是相同的，并且你至少需要砍倒一棵树。
//
//输入：forest = [[1, 2, 3], [0, 0, 4], [7, 6, 5]]
//输出：6
//解释：沿着上面的路径，你可以用 6 步，按从最矮到最高的顺序砍掉这些树。
//
//输入：forest = [[1, 2, 3], [0, 0, 0], [7, 6, 5]]
//输出： - 1
//解释：由于中间一行被障碍阻塞，无法访问最下面一行中的树。
//
//输入：forest = [[2, 3, 4], [0, 0, 5], [8, 7, 6]]
//输出：6
//解释：可以按与示例 1 相同的路径来砍掉所有的树。
//(0, 0) 位置的树，可以直接砍去，不用算步数。
//
//提示：
//	m == forest.length
//	n == forest[i].length
//	1 <= m, n <= 50
//	0 <= forest[i][j] <= 10^9

class Solution {
    int m, n;

public:
    int cutOffTree(vector<vector<int>>& f) {
        m = f.size(), n = f[0].size();
        // 1.准备⼯作：找出砍树的顺序

        vector<pair<int, int>> trees;
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                if (f[i][j] > 1)
                    trees.push_back({ i, j });

        sort(trees.begin(), trees.end(),
            [&](const pair<int, int>& p1, const pair<int, int>& p2) {
                return f[p1.first][p1.second] < f[p2.first][p2.second];
            });
        // 2.按照顺序砍树

        int bx = 0, by = 0;
        int ret = 0;
        for (auto& [a, b] : trees) {
            int step = bfs(f, bx, by, a, b);
            if (step == -1)
                return -1;
            ret += step;
            bx = a, by = b;
        }
        return ret;
    }
    bool vis[51][51];
    int dx[4] = { 0, 0, 1, -1 };
    int dy[4] = { 1, -1, 0, 0 };
    int bfs(vector<vector<int>>& f, int bx, int by, int ex, int ey) {
        if (bx == ex && by == ey)
            return 0;
        queue<pair<int, int>> q;
        memset(vis, 0, sizeof vis); // 清空之前的数据

        q.push({ bx, by });
        vis[bx][by] = true;
        int step = 0;
        while (q.size()) {
            step++;
            int sz = q.size();
            while (sz--) {
                auto [a, b] = q.front();
                q.pop();
                for (int i = 0; i < 4; i++) {
                    int x = a + dx[i], y = b + dy[i];
                    if (x >= 0 && x < m && y >= 0 && y < n && f[x][y] &&
                        !vis[x][y]) {
                        if (x == ex && y == ey)
                            return step;
                        q.push({ x, y });
                        vis[x][y] = true;
                    }
                }
            }
        }
        return -1;
    }
};